// use std::cmp::min;

pub fn dp_rec_mc(amount: u32) -> u32 {
    // 实现⼀个算法，⽤于实现最⼩找零纸币数。
    // 币种含：1、2、5、10、20、30、50、100元。要求：输⼊是⾦额，输出最少的找零纸币数。⽐如输⼊24，输出最⼩找零纸币数：3(⼀张20元、两张2元)。
    // knapsack problem
    let money: Vec<u32> = vec![1, 2, 5, 10, 20, 30, 50, 100];
    let mut volumn = (0..=amount).into_iter().collect::<Vec<u32>>();

    for i in 1..=(amount as usize) {
        for &coin in &money {
            if coin as usize > i {
                break;
            }
            volumn[i] = volumn[i].min(volumn[i-(coin as usize)] + 1);
        }
    }
    volumn[amount as usize]
}
